#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// head -> node1 -> node2 -> NULL
class Solution
{
public:
    void addAtHead(ListNode *&head, ListNode *&pre, ListNode *ptr)
    {
        pre->next = ptr->next;
        ptr->next = head;
        head = ptr;
    }
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr)
            return nullptr;
        ListNode *ptr = head->next, *pre = head;
        while (ptr != nullptr)
        {
            addAtHead(head, pre, ptr);
            ptr = pre->next;
        }
        return head;
    }
};